/*
练习2-1 带空头结点的单链表操作

如果链表采用带空头结点的方式实现，请修改算法 2-7（单链表插入）和算法
2-8（单链表删除），实现相应的插入和删除操作。 函数接口定义：

void Insert (List list, int i, ElemSet x); //* 在单链表 list 的第 i
个位置上插入元素 x

void Remove ( List list, int i );          //* 从单链表 list 中删除第 i 个元素

其中 List 结构定义如下：

typedef struct ListNode *Position; //* 指针即结点位置

struct ListNode {

    ElemSet data;  //* 存储数据

    Position next; //* 线性表中下一个元素的位置

};

typedef struct HeadNode *List;

struct HeadNode {

    Position head; //* 单链表头指针

    int length;    //* 表长

};

函数接口定义中，i 是元素 x 需要被插入或删除的位序（从 1 开始）；ElemSet
是用户定义的数据类型，例如 int、double 或者 char 等。 若传入的位序 i
不是合理的位置，则在一行中打印 ERROR。注意：list 的头指针 head
指向一个空的头结点，这个结点里不存任何真实数据。

输入样例 1：

3: 1 2 5
2 3

输出样例 1：

4: 1 3 2 5

输入样例 2：

6: 4 1 3 2 5 8
3

输出样例 2：

5: 4 1 2 5 8

输入样例 3：

6: 4 1 3 2 5 8
0 0

输出样例 3：

ERROR
6: 4 1 3 2 5 8
*/

#include <stdio.h>
#include <stdlib.h>

typedef int ElemSet;
typedef struct ListNode *Position; /* 指针即结点位置 */
struct ListNode {
    ElemSet data;  /* 存储数据*/
    Position next; /* 线性表中下一个元素的位置 */
};
typedef struct HeadNode *List;
struct HeadNode {
    Position head; /* 单链表头指针 */
    int length;    /* 表长 */
};

void Insert(List list, int i, ElemSet x);
void Remove(List list, int i);

int main(void) {
    int i, n, x;
    Position p;
    List list;

    list = (List)malloc(sizeof(struct HeadNode));
    list->head = (Position)malloc(sizeof(struct ListNode)); /* 创建空头结点 */
    ;
    list->head->next = NULL;
    list->length = 0;
    scanf("%d: ", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d", &x);
        Insert(list, i, x);
    }
    scanf("%d", &i);
    if (scanf("%d", &x) != EOF) {
        Insert(list, i, x);
    } else {
        Remove(list, i);
    }
    printf("%d:", list->length);
    p = list->head->next;
    while (p != NULL) {
        printf(" %d", p->data);
        p = p->next;
    }
    return 0;
}
/* 你的代码将被嵌在这里 */
void Insert(List list, int i, ElemSet x) {
    if (i < 1 || i > list->length + 1) {
        printf("ERROR\n");
        return;
    }
    Position p = list->head;
    for (int j = 1; j < i; j++) {
        p = p->next;
    }
    Position node = (Position)malloc(sizeof(struct ListNode));
    if (node == NULL) {
        printf("Memory allocation error\n");
        return;
    }
    node->data = x;
    node->next = p->next;
    p->next = node;
    list->length++;
}

void Remove(List list, int i) {
    if (i < 1 || i > list->length) {
        printf("ERROR\n");
        return;
    }
    Position p = list->head;
    for (int j = 1; j < i; j++) {
        p = p->next;
    }
    if (p->next == NULL) {
        printf("ERROR\n");
        return;
    }
    Position node = p->next;
    p->next = node->next;
    free(node);
    list->length--;
}